#include <iostream>
#include <vector>

using namespace std;

int minimumTotal(vector<vector<int>> &triangle)
{
    vector<int> dp(triangle.size(), 0);
    for (int i = 0; i < triangle.size(); i++)
    {
        vector<int> temp = triangle[i];
        if (temp.size() > 1)
        {
            dp[temp.size() - 1] = dp[temp.size() - 2] + temp[temp.size() - 1];
        }
        for (int j = temp.size() - 2; j > 0; j--)
        {
            dp[j] = temp[j] + min(dp[j], dp[j - 1]);
        }
        dp[0] += temp[0];
        for (int j = 0; j <= i; j++)
        {
            printf(" %d ", dp[j]);
        }
        printf("\n");
    }
    int res = dp[0];
    for (int i = 1; i < triangle.size(); i++)
    {
        // printf(" %d ", dp[i]);
        res = min(dp[i], res);
    }
    return res;
}

int main()
{
    vector<vector<int>> triangle = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
    int res = minimumTotal(triangle);
    return 0;
}